﻿#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
//160. 相交链表
//给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
//如果两个链表不存在相交节点，返回 null 。
//图示两个链表在节点 c1 开始相交：
//题目数据 保证 整个链式结构中不存在环。
//注意，函数返回结果后，链表必须 保持其原始结构 。
struct ListNode
{
    int val;
    struct ListNode* next;
};

//时间复杂度高的解法为：固定一个链表的节点，然后去遍历另一个链表，时间复杂度为：o(n^2)



//时间复杂度低的做法：
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    if (headA == NULL || headB == NULL)
    {
        return NULL;
    }
    struct ListNode* newhead1 = headA, * newhead2 = headB, * returnhead = NULL;
    int size1 = 0, size2 = 0;
    while (newhead1 != NULL)
    {
        newhead1 = newhead1->next;
        size1++;
    }
    newhead1 = headA;;
    while (newhead2 != NULL)
    {
        newhead2 = newhead2->next;
        size2++;
    }
    newhead2 = headB;
    int distance = size1 > size2 ? size1 - size2 : size2 - size1;
    if (size1 > size2)
    {
        int i = distance;
        while (i > 0)
        {
            newhead1 = newhead1->next;
            i--;
        }
    }
    if (size2 > size1)
    {
        int i = distance;
        while (i > 0)
        {
            newhead2 = newhead2->next;
            i--;
        }
    }
    while (newhead1 && newhead2)
    {
        if (newhead1 == newhead2)
        {
            returnhead = newhead1;
            break;
        }
        newhead1 = newhead1->next;
        newhead2 = newhead2->next;
    }
    return returnhead;
}